from collections import defaultdict, Counter


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False

        diff = [ord(c2)-ord(c1) for c1, c2 in zip(s, t)]
        diff = [x if x > 0 else x+26 for x in diff if x != 0]
        if len(diff) == 0:
            return True
        stat = Counter(diff)
        max_diff, max_cnt = max(stat.items(), key=lambda x: (x[1], x[0]))
        cost = (max_cnt - 1) * 26 + max_diff
        return cost <= k



print(Solution().canConvertString("input", "ouput", 9))
print(Solution().canConvertString("abc", "bcd", 10))
print(Solution().canConvertString("aab", "bbb", 26))
